# -*- coding: utf-8 -*-

class HeapSort:
	"""
		Classe HeapSort
		Parâmetro de entrada:
			A: Lista a ser ordenada
	"""
	def __init__(self, A):
		self.heapsize = len(A)
		self.A = A
		self.sort()

	def left(self, i):
		"""
			Retorna o nó descendente esquerdo do parent de índice i
		"""
		return ((2 * i) + 1)

	def right(self, i):
		"""
			Retorna o nó descendente direito do parent de índice i
		"""
		return ((2 * i) + 2)

	def parent(self, i):
		"""
			Retorna o o nó parent do nó de índice i
		"""
		return int(math.floor((i - 1) / 2))

	def maxHeapify(self, i):
		"""
			Método que verifica que a propriedade de max-heap é cumprida (O root tem o valor máximo da lista)
		"""
		l = self.left(i)
		r = self.right(i)

		largest = l if (l < self.heapsize and self.A[l] > self.A[i]) else i

		largest = r  if (r < self.heapsize and self.A[r] > self.A[largest]) else largest

		if largest != i:
			self.A[i], self.A[largest] = self.A[largest], self.A[i]
			self.maxHeapify(largest)

	def buildMaxHeap(self):
		"""
			Assegura que os nós descendentes estão todos numa max-heap antes de os respectivos nós parent o estarem
		"""
		for k in range(self.heapsize / 2, -1, -1):
			self.maxHeapify(k)

	def sort(self):
		"""
			Método que constroi a heap e ordena os nós
		"""
		self.buildMaxHeap()
		for k in range(len(self.A) - 1, 0, -1):
			self.A[0], self.A[k] = self.A[k], self.A[0]
			self.heapsize -= 1
			self.maxHeapify(0)